class Solution {
    //快排

    // public int[] sortArray(int[] nums) {
    //     qsort(nums,0,nums.length - 1);
    //     return nums;
    // }

    // public void qsort(int[] nums,int left,int right) {
    //     if(left >= right) {
    //         return;
    //     }
    //     int key = nums[new Random().nextInt(right - left + 1) + left];
    //     int l = left,r = right,i = l;
    //     while(i <= r) {
    //         if(nums[i] < key) swap(nums,l++,i++);
    //         else if(nums[i] == key) i++;
    //         else swap(nums,r--,i);
    //     }
    //     qsort(nums,left,l-1);
    //     qsort(nums,r+1,right);
    // }

    // public void swap(int[] nums,int i,int j) {
    //     int tmp = nums[i];
    //     nums[i] = nums[j];
    //     nums[j] = tmp;
    // }

    //归并
    int[] tmp;
    public int[] sortArray(int[] nums) {
        tmp = new int[nums.length];
        mergeSort(nums,0,nums.length - 1);
        return nums;
    }

    public void mergeSort(int[] nums,int left,int right){
        if(left >= right) return;
        int mid = (left + right)/2;

        mergeSort(nums,left,mid);
        mergeSort(nums,mid + 1,right);

        int cur1 = left,cur2 = mid + 1,i = 0;
        while(cur1 <= mid && cur2 <= right) {
            tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums [cur2++];
        }
        while(cur1 <= mid) tmp[i++] = nums[cur1++];
        while(cur2 <= right) tmp[i++] = nums[cur2++];

        for(int j = left;j <= right;j++)
            nums[j] = tmp[j - left];
    }
}